package com.feng.study.demo.sort;

import com.google.common.collect.Lists;

import java.util.ArrayList;
import java.util.Collections;

/**
 * 排序算法底层分析demo
 * Arrays.sort((E[]) elementData, 0, size, c)
 * TimSort（有比较器）和ComparableTimSort（没有比较器）
 * 稳定的
 */
public class TimSortDemo {
    public static void main(String[] args) {
        ArrayList<Integer> list = Lists.newArrayList(1, 2, 3, 4, 5, 7, 6);

        int left = 0;
        int right = 0;
        //无符号右移>>>,有符号右移>>
        int mid = (left + right) >>> 1;

        // 当小于MIN_MERGE = 32的时候，采用插入排序，优化了插入排序
        // 优化一：countRunAndMakeAscending()插入排序前先识别有序列段，翻转；即前面的有序列段不需要遍历做插入排序
        //        如：{1,2,3,4,5,7,6}，有序段为{1,2,3,4,5,7}，只需要对最后一个6做二分插入排序
        // 优化二：插入排序使用二分查找binarySort()

        // 当大于等于MIN_MERGE = 32的时候，采用归并排序(这里没有细看，大概是下面的逻辑)
        // 主要是找到minRun = minRunLength(nRemaining)分段二路归并；(minRun小于MIN_MERGE,一直右移一位，直到满足条件)
        // 先使用上面优化后的插入排序方法，对小段排序；入栈；对有序段做归并；最后对剩余有序段做归并
        Collections.sort(list);
        System.out.println(list);
    }

}
